package com.nanbei.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassDescription: 拓扑排序
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/1 17:49
 */
public class TopologicalSort {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("JavaWeb");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.setEdges(Arrays.asList(new Edge(v3))); // +1
        v2.setEdges(Arrays.asList(new Edge(v3))); // +1
        v3.setEdges(Arrays.asList(new Edge(v4)));
        v6.setEdges(Arrays.asList(new Edge(v4)));
        v4.setEdges(Arrays.asList(new Edge(v5)));
        v5.setEdges(Arrays.asList(new Edge(v7)));
        v7.setEdges(Arrays.asList(new Edge(v5)));

        ArrayList<Vertex> vertices = new ArrayList<>(Arrays.asList(v1, v2, v3, v4, v5, v6, v7));


        // 统计每个顶点的入度数
        for (Vertex vertex : vertices) {
            List<Edge> edges = vertex.getEdges();
            for (Edge edge : edges) {
                Vertex linked = edge.getLinked();
                int penetration = linked.getPenetration();
                linked.setPenetration(penetration+1);
            }
        }
       // 将入度为0的加入到队列中
        LinkedList<Vertex> vertexLinkedList = new LinkedList<>();
        for (Vertex vertex : vertices) {
            if (vertex.getPenetration() == 0){
                vertexLinkedList.offer(vertex);
            }
        }
        // 队列不断移除顶点，没移除一个顶点，把他相邻顶点的度-1，若减到0在入队
        while (!vertexLinkedList.isEmpty()){
            Vertex vertex = vertexLinkedList.poll();
            System.out.println(vertex.getName());
            List<Edge> edges = vertex.getEdges();
            for (Edge edge : edges) {
                Vertex linked = edge.getLinked();
                int penetration = linked.getPenetration();
                linked.setPenetration(penetration-1);
                if (penetration-1 == 0){
                    vertexLinkedList.offer(linked);
                }
            }
        }
    }
}
